class Solution {
    
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int right = 1;

        int[] res = new int[n];
        res[0] = 1;

        for (int i = 1; i < n; i++) {
            res[i] = res[i-1] * nums[i-1];
        }

        for (int i = n-2; i >= 0; i--) {
            right *= nums[i+1];
            res[i] *= right;
        }
        return res;
    }

    public int[] productExceptSelf0(int[] nums) {
        int n = nums.length;
        int[] pre_mul = new int[n+1];
        pre_mul[0] = 1;
        pre_mul[1] = nums[0];
        int[] post_mul = new int[n];
        post_mul[n-1] = 1;

        int[] res = new int[n];

        for (int i = 1; i < n; i++) {
            pre_mul[i+1] = pre_mul[i] * nums[i];
            post_mul[n-i-1] = post_mul[n-i] * nums[n-i];
        }

        for (int i = 0; i < n; i++) {
            res[i] = pre_mul[i]*post_mul[i];
        }
        return res;
    }
}